package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.*;

/**
 * @author waxijiang
 */
public class LevelTraversal {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);
        System.out.printf(String.valueOf(levelOrder(node)));
    }

    /**
     * 层次遍历
     *
     * @param root 　根节点
     * @return 层次遍历结果　例如：[
     * [3],
     * [9,20],
     * [15,7]
     * ]
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 构造辅助队列
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        // 构造返回结果
        List<List<Integer>> result = new ArrayList<>();

        // 排除特殊
        if (root == null) {
            return result;
        } else {
            queue.offer(root);
        }

        // 记录层数
        TreeNode flag = root;
        List<Integer> tmp_list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            tmp_list.add(tmp.val);

            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }

            // 如果是最右边的节点，则该层遍历完毕
            if (tmp == flag) {
                result.add(tmp_list);
                tmp_list = new ArrayList<>();
                // 更新最右边节点
                if (!queue.isEmpty()) {
                    flag = queue.getLast();
                }
            }
        }

        return result;
    }
}
